package me.renyaoxiang.algorithm.sortforstats;


public class MergeSortForStats {
    public static void sort(StatsContext statsContext, int[] data) {
        sortPart(statsContext, data, 0, data.length);
    }

    public static void sortPart(StatsContext statsContext, int[] data, int startInclude, int endExclude) {
        statsContext.callIndexCompare();
        if (startInclude < endExclude  ) {

            statsContext.callIndexCompare();
            if(endExclude-startInclude>=2){

                statsContext.callIndexSign();
                int mid = ((endExclude + startInclude) / 2);

                statsContext.callIndexCompare();
                if (mid < endExclude) {
                    sortPart(statsContext, data, startInclude, mid);
                    sortPart(statsContext, data, mid, endExclude);
                    mergeParts(statsContext, data, startInclude, mid, endExclude);
                } else {
                    sortPart(statsContext, data, startInclude, mid);
                }

            }
        }
    }

    public static void mergeParts(StatsContext statsContext, int[] data, int startInclude, int midIndex, int endExclude) {
        statsContext.callIndexSign();
        int firstStart = startInclude;
        statsContext.callIndexSign();
        int secondStart = midIndex;
        statsContext.callIndexSign();
        int firstCount = midIndex - startInclude;
        statsContext.callIndexSign();
        int secondCount = endExclude - midIndex;

        while (firstCount > 0 && secondCount > 0) {
            statsContext.callIndexCompare();
            statsContext.callIndexCompare();

            statsContext.callCompare();
            if (data[firstStart] <= data[secondStart]) {

                statsContext.callIndexSign();
                firstStart++;

                statsContext.callIndexSign();
                firstCount--;
            } else {
                statsContext.callSign();
                int tempValue = data[secondStart];

                statsContext.callIndexSign();
                for (int i = secondStart; i > firstStart; i--) {
                    statsContext.callIndexSign();
                    statsContext.callIndexCompare();

                    statsContext.callSign();
                    data[i] = data[i - 1];
                }

                statsContext.callSign();
                data[firstStart] = tempValue;

                statsContext.callIndexSign();
                secondStart++;

                statsContext.callIndexSign();
                firstStart++;

                statsContext.callIndexSign();
                secondCount--;
            }
        }
    }
}
